
/**
 * Class CSC-421
 * Instructor: Wilfredo Marrero
 * @author Hyrum Taft, Don Evett
 * @version 9
 * A solution to homework problem 3.
 * Input: The ArrayList data will contain 2 Strings, each containing a sequence of capital letters that results from
   traversing a binary tree whose nodes contain the capital letters. (Note that the binary tree need not be
   a binary search tree. The letters can appear anywhere in the tree.) The first string is the listing of the
   nodes in a pre-order traversal. The second String is a listing of the nodes in an in-order traversal.
 * Output: An ArrayList of one string string Your output ArrayList must contain a single String which is the sequence 
   of letters as they would be encountered in a post-order traversal of the tree.
 * */

import java.io.Console;
import java.util.ArrayList;
import java.util.Collections;



public class Solution {

	private static String output;
	
	/**
	 * @param data will contain 2 Strings. The first string will be the preorder of the output, the second string will be the inorder output
	 * @return An ArrayList containing postorder output of given data found in input parameters 1 and 2
	 */
    public static ArrayList<String> solve(ArrayList<String> data)
    {	
    	output = "";
    	if (data == null || data.size() < 2 || data.size() > 2 ) 
    	{
			return data;
		} 
    	else
    	{
    		FindPostOrderOutputFromPreorderAndInorderOutput(data.get(1), data.get(0), data.get(0).length());
    	}
    	data.clear();
    	data.add(output);
    	System.out.println("Solution: " +  output);
     	return data;
    }
    
    //       left sub tree      right sub tree
    //     root-__  \____   ____/
    //            \  |   | |   |
    // pre-order   Q-Z-B-A-L-R-C
    //                   |	
    //                index of root in in-order  == rootIndex
    //                   |    
    // in-order    B-Z-A-Q-R-C-L
    //             |   |   |   |
    //             -----   -----
    //  left sub tree/       \ right sub tree
    //
    // in-Order -> elements before the root are the left sub tree
    // in-Order -> elements after the root are the right sub tree
    // find the index of root in inOrder and store it as rootIndex
    // pre-Order -> all elements after the rootIndex found in inOrder are the right sub tree
    // pre-Order -> all elements excluding the first, up to and including the location where rootIndex points to are the left sub tree
    // the root is always the last item to be printed in a post order traversal 
    // 
    // post order output BAZCRLQ
    
    public static void FindPostOrderOutputFromPreorderAndInorderOutput(String inOrder, String preOrder, int count )
    {
    	// first find the root index in in-Order
    	int rootIndex = inOrder.indexOf(preOrder.charAt(0));
    	
    	
    	// if there is something on the left meaning, root index isn't 0 then recurse to the next node
    	if(rootIndex != 0)
    	{
    		FindPostOrderOutputFromPreorderAndInorderOutput(inOrder, preOrder.substring(1, preOrder.length()), rootIndex);
    	}
    	
    	// if there is something on the right continue to the right
    	if(rootIndex != count -1)
    	{
    		FindPostOrderOutputFromPreorderAndInorderOutput(
    				inOrder.substring(rootIndex + 1, inOrder.length()), 
    				preOrder.substring(rootIndex + 1, preOrder.length()), 
    				count - rootIndex - 1);
    	}
    	
    	// there is nothing on the left or right
    	// save node for output
    	output += preOrder.charAt(0);
    	System.out.println("output += " + output);
    }
    
}
